Package edu.claflin.finder.logic

Class Graph

  • Direct Known Subclasses:
    ConditionedGraph
    public class Graph
extends java.lang.Object
    Used to represent a graph in memory. Migrated from matrix form, the graph is now kept track of via a list of edges and nodes. All the previous methods remain in existence but the underlying implementation has changed.
    Version:
    3.4 February 2, 2016
    Author:
    Charles Allen Schultz II

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.ArrayList<Edge> edgeList
      The list of edges added to the graph.
      private java.lang.String graphName
      The name of the Graph provided by the user.
      private java.util.ArrayList<Node> nodeList
      The list of the nodes added to the graph.
      protected boolean suppressLog
      Used to suppress logging.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        Graph​(java.lang.String graphName)
      Initializes the graph.
      private Graph​(java.lang.String graphName, java.util.ArrayList<Node> nodeList, java.util.ArrayList<Edge> edgeList)
      Private constructor used by subGraph method.

    • Method Summary

      All Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      boolean addEdge​(int node1Index, int node2Index, java.lang.Object edgeData)
      Deprecated.
      Outdated since v3.
      boolean addEdge​(Edge edge)
      Adds an edge to the Graph.
      boolean addEdge​(java.lang.String node1, java.lang.String node2, java.lang.Object edgeData)
      Deprecated.
      Outdated since v3.
      boolean addEdges​(java.util.List<Edge> edges)
      Adds a list of Edges to the graph.
      void addEdgesBetweenAllNodesInList​(java.util.ArrayList<Node> list)
      Adds edges in between all possible pair combinations of nodes in a list if both nodes involved are present in the graph.
      boolean addNewNode​(java.lang.String node)
      Deprecated.
      Outdated since v3.
      boolean addNode​(Node node)
      Adds a node to the graph.
      boolean addNodes​(java.util.List<Node> nodes)
      Adds a list of nodes to the graph.
      boolean addPartialGraph​(java.util.List<Node> nodes, java.util.List<Edge> edges)
      Adds a partial graph to this graph.
      private void checkNode​(Node node)
      Verifies that the node is NOT in the graph.
      private void checkNodeIndex​(int nodeIndex)
      Deprecated.
      No replacement.
      boolean containsNode​(Node node)
      Checks if the graph contains the given node.
      Graph copy()
      Copies this Graph object using the getSubGraph() method.
      java.util.List<Node> getAdjacencyList​(Node node)
      Obtains an adjacency list for the supplied node based on the Graph.
      int getDegree​(Node n)  
      java.lang.Object getEdge​(int node1Index, int node2Index)
      Deprecated.
      Outdated since v3.
      Edge getEdge​(Node source, Node destination)
      Locates an Edge object in the edgeList and returns it.
      java.lang.Object getEdge​(java.lang.String node1, java.lang.String node2)
      Deprecated.
      Outdated since v3.
      java.util.List<Edge> getEdgeList()
      Returns the list of edges in the graph.
      java.util.ArrayList<Edge> getEdgesBack​(java.util.List<Node> nodes)
      Gets the list edges of this Graph that involve the nodes in the given list
      java.lang.String getName()
      Gets the name of the graph.
      Node getNode​(java.lang.String NodeName)
      Gets a node based on its name.
      int getNodeCount()
      Gets the number of nodes in the graph.
      int getNodeIndex​(Node node)
      Gets the index of a Node object in memory.
      int getNodeIndex​(java.lang.String node)
      Deprecated.
      Outdated since v3.
      java.util.List<Node> getNodeList()
      Returns the list of nodes in the graph.
      java.lang.String getNodeName​(int nodeIndex)
      Deprecated.
      Outdated since v3.
      Graph getSubGraph​(int startNode, int stopNode, java.lang.String nameQualifier)
      Deprecated.
      Outdated since v3.
      Graph getSubGraph​(java.util.ArrayList<java.lang.String> subStringSet, java.lang.String nameQualifier)
      Deprecated.
      Outdated since v3.
      Graph getSubGraph​(java.util.List<Node> nodes, java.lang.String nameQualifier)
      Returns a subGraph of this graph.
      void intersect​(java.util.List<Node> list)
      Intersects this graph's node list with the input list.
      void removeEdgesBetweenAllNodesInList​(java.util.ArrayList<Node> list)
      Removes edges in between all possible pair combinations of nodes in a list if both nodes involved are present in the graph.
      void removeEdgesInvolving​(Node n)
      Remove all the edges in which the given Node participates.
      void removeNode​(Node node)
      Removes a node from the set.
      java.lang.String toString()
      Returns a String representation of the Graph.
      void transferEdgesContainingNodeFromGraph​(Graph graph, Node node)
      Adds all edges containing the input node from the input graph to this graph, provided that the other vertex is already within this graph.
      void transpose​(int node1Index, int node2Index)
      Transposes the specified nodes.
      void transpose​(Node node1, Node node2)
      Transposes the specified nodes.
      void transpose​(java.lang.String node1, java.lang.String node2)
      Deprecated.
      Outdated since v3.
      Graph uniqueCopy()
      Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects.
      Graph uniqueCopy​(java.lang.String gName)  
      java.util.ArrayList<Node> uniqueCopyNodeList()
      Clone method that only clones the node list, done for convenience because lists don't have built in cloning.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    • Field Detail

      • graphName

        private final java.lang.String graphName
        The name of the Graph provided by the user. This value is used by the program to name output files unless specified otherwise.

      • nodeList

        private final java.util.ArrayList<Node> nodeList
        The list of the nodes added to the graph. Used by the program to keep track of the associations within the matrix. It may be re-ordered dynamically at runtime.

      • edgeList

        private final java.util.ArrayList<Edge> edgeList
        The list of edges added to the graph. The graph is, by default, a directed graph. As such, two edges must be added to force the graph to be bidirectional.

      • suppressLog

        protected boolean suppressLog
        Used to suppress logging.

    • Constructor Detail

      • Graph

        public Graph​(java.lang.String graphName)
        Initializes the graph. Merely initializes fields. It does not set any data. Also sets the Logging Utility object. If null, the class will not log data.
        Parameters:
        graphName - the String which represents the name of the Graph.

      • Graph

        private Graph​(java.lang.String graphName,
              java.util.ArrayList<Node> nodeList,
              java.util.ArrayList<Edge> edgeList)
        Private constructor used by subGraph method.
        Parameters:
        graphName - the String which represents the name of the Graph.
        nodeList - the ArrayList of Node objects.
        edgeList - the ArrayList of Edge objects.

    • Method Detail

      • getName

        public java.lang.String getName()
        Gets the name of the graph.
        Returns:
        The graph name.

      • addNewNode

        @Deprecated
public boolean addNewNode​(java.lang.String node)
        Deprecated.
        Outdated since v3. Replaced by {}
        Adds a node to the graph. Adds the specified node name to the nodeList by creating and adding a new node and then calling the addNode(Node) method.
        Parameters:
        node - the String which denotes the name of the node to add.
        Returns:
        true if the addition was successful.

      • addNode

        public boolean addNode​(Node node)
        Adds a node to the graph. Adds a Node object to the graph.
        Parameters:
        node - the Node object to add.
        Returns:
        true if the addition was successful.

      • addNodes

        public boolean addNodes​(java.util.List<Node> nodes)
        Adds a list of nodes to the graph.
        Parameters:
        nodes - the List<Node> containing the nodes to add.
        Returns:
        true if the addition was successful.

      • getNodeIndex

        @Deprecated
public int getNodeIndex​(java.lang.String node)
        Deprecated.
        Outdated since v3. Replaced by {}
        Gets the index of a node based on its name. Maintained with the new implementation to preserve existing uses. Will not match nodes which may have additional properties attached in future implementations.
        Parameters:
        node - the String representing the node to search for.
        Returns:
        the index of the node or -1 if the node was not found.

      • getNodeIndex

        public int getNodeIndex​(Node node)
        Gets the index of a Node object in memory. Retained for older API compatibility. The ordering of the nodes is not guaranteed and may change during the program's runtime.
        Parameters:
        node - the Node object to search for.
        Returns:
        the index of the node or -1 if the node was not found.

      • getNodeCount

        public int getNodeCount()
        Gets the number of nodes in the graph.
        Returns:
        the integer representing the total number of nodes in the graph.

      • getNodeName

        @Deprecated
public java.lang.String getNodeName​(int nodeIndex)
        Deprecated.
        Outdated since v3. No replacement. Obtain the Node data via the Node object.
        Gets the name of the node at the specified nodeIndex. Ensures that the provided integer is within the range of available indices.
        Parameters:
        nodeIndex - the integer representing the index to get from the headerList.
        Returns:
        the String representing the name of the node.

      • getNodeList

        public java.util.List<Node> getNodeList()
        Returns the list of nodes in the graph.
        Returns:
        the List<Node> containing the list of nodes in the graph.

      • getNode

        public Node getNode​(java.lang.String NodeName)
        Gets a node based on its name.
        Parameters:
        NodeName - the String representing the node to search for.
        Returns:
        the node or null if the node was not found.

      • addEdge

        @Deprecated
public boolean addEdge​(int node1Index,
                       int node2Index,
                       java.lang.Object edgeData)
        Deprecated.
        Outdated since v3. Replaced by {}
        Adds an edge connecting the specified nodes in the Graph. Sets the object data for the edge dependent upon the supplied parameter.
        Parameters:
        node1Index - the integer value indicating the first node.
        node2Index - the integer value indicating the second node.
        edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).
        Returns:
        true if the addition was successful.

      • addEdge

        @Deprecated
public boolean addEdge​(java.lang.String node1,
                       java.lang.String node2,
                       java.lang.Object edgeData)
        Deprecated.
        Outdated since v3. Replaced by {
        Adds an edge connecting the specified nodes to the Graph. This is a convenience method for adding an edge using node names. Graphs are undirected so the order of the parameters does not matter.
        Parameters:
        node1 - the String indicating the first node.
        node2 - the String indicating the second node.
        edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).
        Returns:
        true if the addition was successful.

      • addEdge

        public boolean addEdge​(Edge edge)
        Adds an edge to the Graph. If any edge already exists within the Graph connecting the two supplied nodes or either of the two nodes is not in the nodeList, then the edge is not added.
        Parameters:
        edge - the Edge object to add to the graph.
        Returns:
        true if the addition was successful.

      • addEdges

        public boolean addEdges​(java.util.List<Edge> edges)
        Adds a list of Edges to the graph.
        Parameters:
        edges - the List<Edge> containing the edges to add.
        Returns:
        true if the addition was successful.

      • getEdge

        @Deprecated
public java.lang.Object getEdge​(int node1Index,
                                int node2Index)
        Deprecated.
        Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
        Gets the value of the edge between the specified nodes.
        Parameters:
        node1Index - the integer value of the first node.
        node2Index - the integer value of the second node.
        Returns:
        the Object representing the edge relationship.

      • getEdge

        @Deprecated
public java.lang.Object getEdge​(java.lang.String node1,
                                java.lang.String node2)
        Deprecated.
        Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
        Gets the value of the edge between the specified nodes. This is a convenience method for getting the edge using the node's String name.
        Parameters:
        node1 - the String of the first node.
        node2 - the String of the second node.
        Returns:
        the Object representing the edge relationship.

      • getEdge

        public Edge getEdge​(Node source,
                    Node destination)
        Locates an Edge object in the edgeList and returns it. Note that it will also return an edge with the provided source and destination parameters swapped IF AN ONLY IF said edge is undirected.
        Parameters:
        source - the source Node of the edge.
        destination - the destination Node of the edge.
        Returns:
        the Edge object or null if not found.

      • getEdgeList

        public java.util.List<Edge> getEdgeList()
        Returns the list of edges in the graph.
        Returns:
        the List<Edge> containing the list of edges in the graph.

      • addPartialGraph

        public boolean addPartialGraph​(java.util.List<Node> nodes,
                               java.util.List<Edge> edges)
        Adds a partial graph to this graph. Specifically adds a set of nodes and a set of edges to the graph. It should be noted that nodes or edges in the graph already that attempt to be added again may cause exceptions to occur. Additionally, Nodes are added before Edges so any Edges that depend on Nodes in the add list may be safely added simultaneously. This method is the backbone structure for adding any component to the graph as all other addition methods filter through here.
        Parameters:
        nodes - the List<Node> containing the nodes to add.
        edges - the List<Edge> containing the edges to add.
        Returns:
        true, always. Allows overriding in subclasses which wish to change base implementation.

      • getSubGraph

        @Deprecated
public Graph getSubGraph​(int startNode,
                         int stopNode,
                         java.lang.String nameQualifier)
        Deprecated.
        Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
        Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
        Parameters:
        startNode - the integer pointing to the start node.
        stopNode - the integer pointing to the stop node.
        nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.
        Returns:
        the Graph object representing a subgraph of the original.

      • getSubGraph

        @Deprecated
public Graph getSubGraph​(java.util.ArrayList<java.lang.String> subStringSet,
                         java.lang.String nameQualifier)
        Deprecated.
        Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
        Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
        Parameters:
        subStringSet - an ArrayList containing the String names of the desired nodes.
        nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.
        Returns:
        the Graph object representing a subgraph of the original.

      • getSubGraph

        public Graph getSubGraph​(java.util.List<Node> nodes,
                         java.lang.String nameQualifier)
        Returns a subGraph of this graph. Isolates and extracts a subgraph based on a user supplied node list. The new Graph is a quasi-separate Graph. Each node utilized is directly related between the two graphs and, as such, changes to the properties of one node in the subgraph will be reflected in the super graph. To obtain an independent graph
        Parameters:
        nodes - the List<Node> containing the Node references.
        nameQualifier - the String to differentiate the Graph names.
        Returns:
        the Graph representing the subgraph.

      • transpose

        public void transpose​(int node1Index,
                      int node2Index)
        Transposes the specified nodes. Swaps the location of the nodes in memory. Specifically swaps the nodes in the nodeList as the Edge data has been uncoupled from the Node data. Newer implementation is dependent upon the int based method for performance.
        Parameters:
        node1Index - the integer index of the first node.
        node2Index - the integer index of the second node.

      • transpose

        @Deprecated
public void transpose​(java.lang.String node1,
                      java.lang.String node2)
        Deprecated.
        Outdated since v3. Replaced by {}
        Transposes the specified nodes. Swaps the location of the nodes in memory. This is a convenience method for transposing the nodes based on the Sting representation of the nodes.
        Parameters:
        node1 - the String name of the first node.
        node2 - the String name of the second node.

      • transpose

        public void transpose​(Node node1,
                      Node node2)
        Transposes the specified nodes. Relies on the integer based method for carrying out the operation.
        Parameters:
        node1 - the Node object in the first position.
        node2 - the Node object in the second position.

      • getAdjacencyList

        public java.util.List<Node> getAdjacencyList​(Node node)
        Obtains an adjacency list for the supplied node based on the Graph.
        Parameters:
        node - the Node to obtain the adjacency list for.
        Returns:
        the List<Node> containing the adjacent Nodes.

      • checkNode

        private void checkNode​(Node node)
        Verifies that the node is NOT in the graph. Checks to see if the provided node name is in the headerList and, hence, the dataMatrix. This is an internal method used to ensure that the algorithm is operating correctly.
        Parameters:
        node - the Node to check for.

      • checkNodeIndex

        @Deprecated
private void checkNodeIndex​(int nodeIndex)
        Deprecated.
        No replacement. Further operations shall utilize {)}
        Verifies that the nodeIndex is valid. Ensures that the node does not fall out of bounds. This is an internal method used to ensure that the algorithm is operating correctly.
        Parameters:
        nodeIndex - the integer of the node to check for.

      • copy

        public Graph copy()
        Copies this Graph object using the getSubGraph() method.
        Returns:
        a Graph object identical to the original.

      • uniqueCopy

        public Graph uniqueCopy()
        Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects. I.e. there are no shared nodes or edges between the two graphs. Mathematically speaking: x.getNodeList().get(0) != y.getNodeList().get(0) under any circumstances. The Nodes and Edges may remain equivalent via the equals() implementation. Further, Edge data shall remain entangled due to implementation details.
        Returns:
        a unique copy of the graph object.

      • uniqueCopy

        public Graph uniqueCopy​(java.lang.String gName)

      • uniqueCopyNodeList

        public java.util.ArrayList<Node> uniqueCopyNodeList()
        Clone method that only clones the node list, done for convenience because lists don't have built in cloning. *
        Returns:
        a unique copy of the graph's node list

      • intersect

        public void intersect​(java.util.List<Node> list)
        Intersects this graph's node list with the input list.
        Parameters:
        list - the list to intersect with

      • removeNode

        public void removeNode​(Node node)
        Removes a node from the set. Only used with the Bron-Kerbosch algorithm right now, hopefully doesn't break anything Does NOT affect edges!!!!!!! At time of writing may cause issues if you rely on it to do so
        Parameters:
        node - the node to remove

      • removeEdgesInvolving

        public void removeEdgesInvolving​(Node n)
        Remove all the edges in which the given Node participates.
        Parameters:
        n - the participating Node

      • transferEdgesContainingNodeFromGraph

        public void transferEdgesContainingNodeFromGraph​(Graph graph,
                                                 Node node)
        Adds all edges containing the input node from the input graph to this graph, provided that the other vertex is already within this graph. Probably not very efficient
        Parameters:
        graph - the graph
        node - the node

      • containsNode

        public boolean containsNode​(Node node)
        Checks if the graph contains the given node.
        Parameters:
        node - the node to check for
        Returns:
        whether or not node is in this graph

      • addEdgesBetweenAllNodesInList

        public void addEdgesBetweenAllNodesInList​(java.util.ArrayList<Node> list)
        Adds edges in between all possible pair combinations of nodes in a list if both nodes involved are present in the graph.
        Parameters:
        list - The list of nodes

      • removeEdgesBetweenAllNodesInList

        public void removeEdgesBetweenAllNodesInList​(java.util.ArrayList<Node> list)
        Removes edges in between all possible pair combinations of nodes in a list if both nodes involved are present in the graph. When used with Bron-Kerbosch bipartite, this removes all nodes since the precondition is that this is only used on the nodes in a single group, which are not supposed to have any edges to begin with.
        Parameters:
        list - The list of nodes

      • getEdgesBack

        public java.util.ArrayList<Edge> getEdgesBack​(java.util.List<Node> nodes)
        Gets the list edges of this Graph that involve the nodes in the given list
        Parameters:
        nodes - the list of nodes to found the edges from
        Returns:
        the list edges of this Graph that involve the nodes in the given list

      • getDegree

        public int getDegree​(Node n)

      • toString

        public java.lang.String toString()
        Returns a String representation of the Graph.
        Overrides:
        toString in class java.lang.Object
        Returns:
        the String representation of the Graph.